import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:${USER}
 * Date:${YEAR}-${MONTH}-${DAY}
 * ${TIME}
 */
public class Main {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> setList=new HashSet<>();
        for (String s:wordList) {
            setList.add(s);
        }
        Set<String> vis=new HashSet<>();
        if(!setList.contains(endWord))return 0;
        Queue<String> q=new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);
        int step=0;
        while (!q.isEmpty()){
            step++;
            int size=q.size();
            for (int i = 0; i < size; i++) {
                String s=q.poll();
                for(int j=0;j< s.length();j++){
                    char[] tmp=s.toCharArray();
                    for (char k = 'a'; k <='z' ; k++) {
                        tmp[j]=k;
                        String ret=new String(tmp);
                        if(setList.contains(ret)&&!vis.contains(ret)){
                            if(ret.equals(endWord))return step+1;
                            q.add(ret);
                            vis.add(ret);
                        }
                    }
                }
            }
        }
        return 0;
    }
}